package com.leetcode.algorithm.y22.m08.w2;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 450. 删除二叉搜索树中的节点
 * 
 * https://leetcode.cn/problems/delete-node-in-a-bst/
 * 
 * @author jie.deng
 *
 */
class Question0450Solution01 {

	public TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
		if (root.val == key) {
			if (root.left == null && root.right == null) {
				return null;
			} else if (root.left == null) {
				return root.right;
			} else if (root.right == null) {
				return root.left;
			}
			TreeNode prev = root;
			TreeNode successor = root.right;
			while (successor.left != null) {
				prev = successor;
				successor = prev.left;
			}
			if (prev == root) {
				successor.left = root.left;
			} else {
				prev.left = successor.right;
				successor.left = root.left;
				successor.right = root.right;
			}
			return successor;
		} else if (root.val > key) {
			root.left = deleteNode(root.left, key);
		} else {
			root.right = deleteNode(root.right, key);
		}
		return root;
	}

}